import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class imp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

public class text {
    public static void main3(String[] args) {
        int[] arr = {27, 15, 19, 18, 28};
        System.out.println(Arrays.toString(smallestK(arr, 3)));
    }

    public static void main2(String[] args) {
        //默认以小根堆形式存放
        //传入的对象必须要能够比较大小
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(5);
        priorityQueue.offer(10);
        priorityQueue.offer(6);

        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
    }

    public static void main(String[] args) {
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        TextHeap textHeap = new TextHeap();
        textHeap.initElem(array);
        textHeap.createHeap();
        textHeap.push(10);
        textHeap.heap_sort();


        for (int i = 0; i < textHeap.usedSize; i++) {
            System.out.print(textHeap.elem[i]);
            if (i < textHeap.usedSize - 1) {
                System.out.print(",");
            }

        }
    }


    //TOP-K问题：建立有 k 个元素的大根堆，并把前 k 个元素存放进大根堆
    //将后面的元素依次与大根堆的最大元素比较，比堆顶元素小，入堆

    public static int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr.length == 0 || k == 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new imp());

        //建立一个大根堆,并且将前三个元素存放在大根堆里
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        //向后遍历元素，arr[i] < top 就入堆
        for (int i = k; i < arr.length; i++) {
            if (!priorityQueue.isEmpty() && arr[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        for (int o = 0; o < k; o++) {
            ret[o] = priorityQueue.poll();
        }
        return ret;
    }
}
